package main

import (
	"fmt"
	"os"
)

/*
1、需求
google公司的一个上机题：
有一个公司，当有新的员工来报道时，要求将该员工的信息加入id，性别，年龄...，
当输入该员工的id时，要求查找到该员工的所有信息
2、要求
不使用数据库
尽量节省内存
速度越快越好=>哈希表（散列）
3、哈希表介绍
散列表是根据关键码值而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表
*/
//定义emp
type Emp struct {
	Id   int
	Name string
	Next *Emp
}

func (this *Emp) ShowMe() {
	fmt.Printf("链表%d找到该雇员%d 姓名=%s\n", this.Id%7, this.Id, this.Name)
}

//定义EmpLink
//这里的EmpLink不带表头，即第一个节点就存放雇员
//指向Emp
type EmpLink struct {
	Head *Emp
}

//定义hashtable，含有一个链表数组
type HashTable struct {
	LinkArr [7]EmpLink
}

//1添加员工的方法，保证添加时，编号是从小到大
func (this *EmpLink) Insert(emp *Emp) {
	cur := this.Head   //辅助指针
	var pre *Emp = nil //辅助指针，pre在cur前面
	//如果当前的EmpLink就是一个空链表
	if cur == nil {
		this.Head = emp //完成
		return
	}
	//如果不是一个空链表，给emp找到对应的位置并插入
	//思路是让cur和emp比较，然后让pre保持在cur前面
	for {
		if cur != nil {
			//比较
			if cur.Id >= emp.Id {
				//找到位置
				break
			}
			pre = cur //保证同步
			cur = cur.Next
		} else {
			break
		}
	}
	//退出时，我们看下是否将emp添加到链表最后
	// if cur==nil{
	// 	pre.Next=emp
	// 	emp.Next=cur
	// }
	pre.Next = emp
	emp.Next = cur
}

//显示链表的信息
func (this *EmpLink) ShowLink(no int) {
	if this.Head == nil {
		fmt.Printf("链表%d 为空\n", no)
		return
	}
	//遍历当前的链表，并显示数据
	cur := this.Head //辅助指针
	for {
		if cur != nil {
			fmt.Printf("链表%d 雇员id=%d 名字=%s ->", no, cur.Id, cur.Name)
			cur = cur.Next
		} else {
			break
		}
	}
	fmt.Println()
}

//根据id查找对应的雇员，如果没有就返回nil
func (this *EmpLink) FindById(id int) *Emp {
	cur := this.Head
	for {
		if cur != nil && cur.Id == id {
			return cur
		} else if cur == nil {
			break
		}
		cur = cur.Next
	}
	return nil
}

//给hashtable编写Insert雇员的方法
func (this *HashTable) Insert(emp *Emp) {
	//使用散列函数确定将该雇员添加到哪个链表
	linkNo := this.HashFun(emp.Id)
	//使用对应的链表添加
	this.LinkArr[linkNo].Insert(emp)
}

//编写方法，显示hashtable的所有雇员
func (this *HashTable) ShowAll() {
	for i := 0; i < len(this.LinkArr); i++ {
		this.LinkArr[i].ShowLink(i)
	}
}

//编写一个散列方法
func (this *HashTable) HashFun(id int) int {
	return id % 7 //得到一个值，就是对应链表的下标
}

//编写一个方法，完成查找
func (this *HashTable) FindById(id int) *Emp {
	//使用散列函数，确定该雇员应该在哪个链表
	linkNo := this.HashFun(id)
	return this.LinkArr[linkNo].FindById(id)
}
func main() {
	key := ""
	id := 0
	name := ""
	var hashtable HashTable
	for {
		fmt.Println("========雇员系统菜单=========")
		fmt.Println("input表示添加雇员")
		fmt.Println("show表示显示雇员")
		fmt.Println("find表示查找雇员")
		fmt.Println("exit表示退出系统")
		fmt.Scanln(&key)
		switch key {
		case "input":
			fmt.Println("输入雇员id")
			fmt.Scanln(&id)
			fmt.Println("输入雇员name")
			fmt.Scanln(&name)
			emp := &Emp{
				Id:   id,
				Name: name,
			}
			hashtable.Insert(emp)
		case "show":
			hashtable.ShowAll()
		case "find":
			fmt.Println("请输入id号：")
			fmt.Scanln(&id)
			emp := hashtable.FindById(id)
			if emp == nil {
				fmt.Printf("id=%d的雇员不存在\n", id)
			} else {
				//编写一个方法，显示雇员信息
				emp.ShowMe()
			}
		case "exit":
			os.Exit(0)
		default:
			fmt.Println("输入错误")
		}

	}
}
